﻿#define  _CRT_SECURE_NO_WARNINGS  1

/*
* 
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include<stdio.h>
#include<assert.h>  // 断言
#include<stdlib.h>  
#include<stdbool.h>   // bool 布尔值

#define OCE 2             // 扩容的倍数
typedef char STDatatype;   // 定义该栈中的数据类型


/*
* 创建栈的结构体
*/
typedef struct Stack
{
	STDatatype* data;     //动态顺序表开辟空间
	int top;              // 栈顶的标识
	int copacity;         // 栈容量

}ST;


/*
* 初始化栈
*/
void StackInit(ST* st)
{
	assert(st); // 断言，判断st 不为 NULL；

	st->data = (STDatatype*)malloc(sizeof(STDatatype) * OCE);

	// 判断动态内存(堆上)开辟的空间是否成功
	if (NULL == st->data)
	{
		perror("st->data 动态开辟空间");
		exit(-1);  // 非正常中止程序
	}

	st->copacity = 2;   // 当前栈的容量
	st->top = 0;        // 栈顶位置

	/*
	* top = 0 ,表示的是栈顶的位置是该最后元素的下一个元素的位置
	* top = 1; 表示的是栈顶的位置就是该最后元素的位置
	*/
}



/*
* 销毁栈
*/
void StackDestory(ST* st)
{
	assert(st);   // 断言，st是否为空

	free(st->data);  // 释放该内存空间
	st->data = NULL; // 手动置为NULL，防止非法访问
	st->copacity = 0;
	st->top = 0;

}



// 栈顶入栈操作
void StackPush(ST* st, STDatatype x)
{
	assert(st);  // 断言判断,st是否为NULL

	// 判断栈是否满了，满了扩容
	if (st->copacity == st->top)
	{
		// 动态(堆区)扩容开辟空间
		STDatatype* tmp = (STDatatype*)realloc(st->data, st->copacity * OCE * sizeof(STDatatype));

		// 判断动态内存开辟空间是否成功
		if (NULL == tmp)
		{
			perror("tmp 扩容");      // 打印错误报告
			exit(-1);                // 非正常退出
		}
		else
		{
			// 动态开辟空间成功,转移主权
			st->data = tmp;
			st->copacity *= OCE;  // 栈容量扩张
		}
	}

	st->data[st->top] = x;    // 栈顶入栈数值
	st->top++;                // 栈顶加加

}



/*
* 栈顶出栈操作
*/
void StackPop(ST* st)
{
	assert(st);          // 断言判断，st 是否为 NULL

	assert(st->top > 0);   // 出栈的位置必须大于 0 ，不能一直删除没了吧

	st->top--;           // 栈顶位置减减一下，就好了
	/*
	* 注意不可以把 st->data[st->top] = 0; 置为 0 的方式
	* 因为可能你存放的数值就是 0 呢，不就有误导了吗
	*/
}



/*
* 取出栈顶元素
*/
STDatatype StackTop(ST* st)
{


	assert(st);  // 断言判断，st 是否为NULL

	assert(st->top > 0);  // 栈不为空

	return st->data[st->top - 1];
	/*
	* -1 ，是因为这里的top 初始化是 0
	* 其top所指向的位置是 该最后一个元素的下一个位置
	*/
}



/*
* 求出栈顶元素的个数
*/
int StackSize(ST* st)
{
	assert(st);  // 断言，判断st 是否为 NULL

	return st->top;
	/*
	* 因为是数组，从0 下标开始，但是计数是要 +1 的
	* 而top 刚好就是下一个元素的位置与 计数值相同
	*/
}



/*
* 判断该栈是否为空栈
*/
bool StackEmpty(ST* st)
{
	return 0 == st->top;
	/*
	* 判断栈是否为空
	* 当栈顶 top 为 0 是：表示栈没有一个数据，为空栈，返回 false (0)
	* 当栈顶 top 不是 0 时，栈不为空，返回 true (1);
	*/
}


bool isValid(char* s) {
	ST st;
	StackInit(&st);

	while (*s)
	{

		switch (*s)  // *s != '\0' ; 字符串结束了停止循环
		{
		case '(':
		case '{':
		case '[':
			StackPush(&st, *s);  // 左括号入栈
			++s;                // 移动字符串位置
			break;
		case '}':
		case ']':
		case ')':
		{          // 右括号，出栈，并判断是否匹配，
			if (StackEmpty(&st))  //  栈为空，字符串没有入栈过，直接就是不匹配 返回 false,
			{
				StackDestory(&st);  // 清空栈
				return false;

			}

			char top = StackTop(&st);  // 取出栈顶数据
			StackPop(&st);             // 和出栈一起，才能取到后面的数据

			// 取出栈顶，判断是否匹配，注意栈顶取出的数据是 左括号的
			if ((*s == '}') && (top != '{') ||
				(*s == ')') && (top != '(') ||
				(*s == ']') && (top != '['))
			{  // 不匹配，清空栈，返回 false
				StackDestory(&st);
				return false;
			}
			else   // 左右括号匹配，移动字符继续匹配判断
			{
				++s;  // 移动字符串位置
			}
		}
		break;

	define:  // 防止特殊情况，
		break;

		}

	}


	// 跳出循环，字符串遍历结束，
	bool ret = StackEmpty(&st);  // 判断栈是否为 空，为空，说明全部匹配，返回 true, 不为空，
	StackDestory(&st);           // 则说明，存在不匹配的左括号，返回 false
	return ret;

}

/*****************************************************************************************************
/*****************************************************************************************************
/*****************************************************************************************************
/*****************************************************************************************************
/*****************************************************************************************************
*/

/*
* 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/implement-stack-using-queues
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/


typedef int QDataType;    // 定义存放队列中的数据类型

typedef struct QueueNode   // 创建队列结构体
{
	struct QueueNode* next;   // 节点指针，注意这里，不可以是 QNode* next ，因为执行顺序的原因，它还没有创建
	QDataType data;           // 别名上的使用 。存在的数据

}QNode;


typedef struct Queue       // 创建队列，队头，队尾的结构体
{
	QNode* head;          // 队列的首节点
	QNode* tail;          // 队列的尾节点

}Queue;



// 初始化队列
void QueueInit(Queue* pq)
{
	pq->head = NULL;
	pq->tail = NULL;

}



// 删除队列
void QueueDestory(Queue* pq)
{
	assert(pq);   // 断言，队列不为空(NULL)

	QNode* cur = pq->head;    // 拷贝队头的地址，用于移动

	while (cur)
	{
		QNode* next = cur->next;   // 拷贝下一个节点的地址，用于释放空间，防止丢失整个队列
		free(cur);   // 释放队头节点的空间
		cur = next;  // 移动节点
	}

	// 同时把队头队尾的空间释放掉，并置为 NULL,防止非法访问
	pq->head = NULL;
	pq->tail = NULL;

}



// 队尾，入队
/*
* 两种情况
* 1. 首个数据入队
* 2. 存在多个数据入队
*/
void QueuePush(Queue* pq, const QDataType x)
{
	assert(pq);    // 队列不为 NULL

	QNode* newNode = (QNode*)malloc(sizeof(QNode));    // 注意可以的类型是队列的结构体类

	if (NULL == newNode)               // 判断开辟空间是否成功
	{
		perror("创建节点失败");
		exit(-1);    // 非正常结束程序

	}
	else         // 否则创建节点成功，赋值初始化
	{
		newNode->data = x;
		newNode->next = NULL;
	}

	if (pq->head == NULL)    // 第一个数据，队尾入队
	{
		pq->head = newNode;       // 第一个数据，队尾，队头都是指向同一个节点的地址的
		pq->tail = newNode;
	}
	else                      // 存在多个数据，队尾入队
	{
		pq->tail->next = newNode;     // 插入节点
		pq->tail = newNode;           // 插入数据后，重新定义队尾的位置
	}

}


/*
// 队头，出队
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);   // pq->head 首节点不为空

	Queue* next = pq->head ->next;  // 拷贝保存到首节点下一个节点的地址，防止在释放空间上，丢失了整个队列
	free(pq->head);     // 释放首节点的空间
	pq->head = next;    // 重新指向新的首节点
	/*但是这里存在一个问题就是
	当出队时只有一个节点时，
	head 头为空的 队头出队为空的话，没有关系会判断断言
	但是队尾 tail， 尾节点释放了空间，但是没有置为 NULL,还会访问该空间，但是这个空间
	已经不是它的了，这是非法访问了，非法访问，是会出错的，
	所以我们需要将尾节点置为空NULL,防止被访问，

}*/
// 优化
// 队头，出队
void QueuePop(Queue* pq)
{
	assert(pq);         // 断言 队列不为空(NULL)
	/*
	if(NULL == pq->head)
	{
		return ;
	}
	*/
	assert(pq->head);   // pq->head 首节点不为空(NULL)

	if (NULL == pq->head->next)    // 为空的话，表示只剩下，最后一个尾节点了
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;   // 首节点和尾节点都置为NULL

	}
	else   // 存在多个节点拷贝释放
	{
		QNode* next = pq->head->next;  // 拷贝保存到首节点下一个节点的地址，防止在释放空间上，丢失了整个队列
		free(pq->head);     // 释放首节点的空间
		pq->head = next;    // 重新指向新的首节点
	}


}





// 取队头数据
QDataType QueueFront(const Queue* pq)
{
	assert(pq);         // 队列不为空(NULL)
	assert(pq->head);   // 队头不为空(NULL)

	return pq->head->data;   // 返回队头数据
}



// 取队尾数据
QDataType QueueBack(const Queue* pq)
{
	assert(pq);          // 队列不为空 (NULL)
	if (NULL == (pq->tail))
	{
		return NULL;
	}


	return  pq->tail->data;    // 返回队尾数据
}



// 计算队列中存在多少元素
int QueueSize(const Queue* pq)
{
	assert(pq);    // 断言 队列不为空(NULL)
	assert(pq->head);  // 断言  队头也不为空(NULL)

	int count = 0;     // 计数
	QNode* cur = pq->head;    // 拷贝队头，代替队头移动，防止丢失整个队列

	while (cur)       // 队头不为空，
	{
		count++;
		cur = cur->next; // 移动节点
	}

	return count;     // 返回计数结果
}



// 判断队列是否为空队列
bool QueueEmpty(const Queue* pq)
{
	assert(pq);    // 断言 队列不为空(NULL)

	return NULL == pq->head;   // 判断一个队列是否为空，判断一下首节点是否为空就可以了，空,返回 true, 非空,返回 false
}


typedef struct {   // 定义队列结构体的栈
	Queue q1;
	Queue q2;

} MyStack;

// 初始化队列，
MyStack* myStackCreate() {
	MyStack* ps = (MyStack*)malloc(sizeof(MyStack));  // 为该栈动态开辟空间

	if (NULL == ps)   // 动态内存堆区上开辟失败
	{
		perror("malloc error");
		exit(-1);
	}
	else
	{   // 调用队列中的函数初始化队列
		QueueInit(&ps->q1);
		QueueInit(&ps->q2);
	}

	return ps;  // 返回初始化的地址

}

// 入栈
void myStackPush(MyStack* obj, int x) {
	/* 将不为空的其中的一个队列进行入栈，也就是入队列操作
	*/

	if (!QueueEmpty(&obj->q1))  // 队列不为空
	{
		QueuePush(&obj->q1, x);

	}
	else
	{
		QueuePush(&obj->q2, x);
	}


}

// 出栈
int myStackPop(MyStack* obj) {
	/*
	先假定一个队列为空，再进行判定是否正确，不正确再修改，修正
	把其中一个不为空的队列除去最后一个数据，其余的全部导入到 另外一个空的队列当中去
	，循环导入完，出栈就是，取出导入之前的还剩下的最后一个数据，就是出栈了
	*/
	Queue* emptyQ = &obj->q1;
	Queue* notemptyQ = &obj->q2;

	if (!QueueEmpty(&obj->q1))   // 修正，空队列
	{
		notemptyQ = &obj->q1;
		emptyQ = &obj->q2;
	}

	while (QueueSize(notemptyQ) > 1) // 循环导入另外一个空队列，剩下最后一个
	{
		QueuePush(emptyQ, QueueFront(notemptyQ));
		QueuePop(notemptyQ);
	}


	int top = QueueBack(notemptyQ);
	QueuePop(notemptyQ);

	return top;


}

// 取栈顶数据
int myStackTop(MyStack* obj) {

	/*
	  判断哪个队列不为空，取其中的最后一个数据，就是取栈顶数据了
	*/
	if (!QueueEmpty(&obj->q1)) // 
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}


}

// 判断栈是否为空
bool myStackEmpty(MyStack* obj) {
	/*
	判断两个队列为空时，则表示 栈为空
	*/

	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);

}

// 清空栈
void myStackFree(MyStack* obj) {
	/*
	把定义的栈的两个队列释放空间
	*/
	QueueDestory(&obj->q1);
	QueueDestory(&obj->q2);

	free(obj);

}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/

